/*
请编写函数 void inverse( LinkList )，实现单链表的原地置逆。即利用原来的结点将线性表：L =（a1, a2, …… , an）

变换为：L =（ an,  …… , a2, a1）

说明：本题目为经典的单链表算法设计题目，简单而有内涵。预设代码中仅用到了C++中的个别东西，但没有采用面向对象的编程方式。
*/

/*
测试用例1:
输入：
10 20 30 40 -1↵
输出：
List:40,30,20,10,↵
List:10,20,30,40,↵

测试用例2:
输入：
10 -1↵
输出：
List:10,↵
List:10,↵
*/

// 以下是预设代码
/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */  
 
#include <iostream>
using namespace std;
  
typedef int ElemType;

// 定义节点
typedef struct node
{
    ElemType data;
    struct node * next;
} NODE;

// 链表：用指向头节点的指针表示
typedef NODE * LinkList;
  
void output( LinkList ); // 打印链表
void change( int, int, NODE * ); // 与本题无关
LinkList createList( ElemType ); // 创建链表
void inverse( LinkList ); // 链表反转

// 创建链表
LinkList createList( ElemType finish )  // finish：数据结束标记
{
    ElemType x;  
    NODE *newNode;
    
    // 建立头结点
    LinkList first = new NODE;
    first->next = NULL;
    first->data = finish;
    
    // 输入数据
    cin >> x;
    
    // 输入finish时，终止输入
    while ( x != finish )
    {
        // 建立新结点，并插入
        newNode = new NODE;
        newNode->data = x; // 数值
        newNode->next = first->next;
        first->next = newNode;
        
        // 输入数据
        cin >> x;
    }
    
    // 返回头节点（链表）
    return first;
}

// 打印链表
void output( LinkList head )
{
    cout << "List:";
    
    // 循环打印
    while ( head->next != NULL )
    {
        cout << head->next->data << ",";  
        head = head->next;  
    }
    cout << endl;
}

// 链表的反转操作
void inverse( LinkList head )
{
    // 改变p1、p2两节点之间的指向关系
    NODE * p1 = head;
    NODE * p2 = head->next;
    
    // 临时指针
    NODE * temp;
    
    while(p2 != nullptr)
    {
        temp = p2->next;
        p2->next = p1;
        
        // 链表尾部指向空
        if (p1->data == -1)
            p2->next = NULL;
        
        p1 = p2;
        p2 = temp;
    }
  
    // 改变头节点指向
    head->next = p1;
}

int main(int argc, char** argv)   
{
    LinkList head;
    head = createList( -1 );
    output( head );
    inverse( head );
    output( head );
    return 0;
}
  
/* PRESET CODE END - NEVER TOUCH CODE ABOVE */  